/*----------------------------------------------------------------------------------------
*
*  Copyright 2019, Gao Hai Hui, <fromzeropoint@126.com>.  All rights reserved.
*  https://gitee.com/helloworldghh/xoskit.git
*  Use of this source code is governed by a MIT license
*  that can be found in the License file.
*
----------------------------------------------------------------------------------------*/
#ifndef __XOS_STL_POOL_LOCK_FREE_QUEUE_H__
#define __XOS_STL_POOL_LOCK_FREE_QUEUE_H__

#include <cstdint>
#include <atomic>
#include <thread>

namespace xos_stl
{
    namespace lock_free
    {
        /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 
        // 对齐alloc,free方法类
        // 
        class aligned_alloc_and_free
        {
        public:
            aligned_alloc_and_free(){}
            ~aligned_alloc_and_free(){}
        public:
#if defined( XOS_X64 )
            void * aligned_alloc( size_t size, size_t alignment )
            {
                void * pRet = 0;
                pRet = _aligned_malloc( size, alignment );
                return pRet;
            }
            void aligned_free( void * ptr )
            {
                _aligned_free( ptr );
            }
#else
            void * aligned_alloc( size_t size, size_t alignment )
            {
                void * pRet = 0;
                posix_memalign( &pRet, alignment, size );
                return pRet;
            }
            void aligned_free( void * ptr )
            {
                free( ptr );
            }
#endif
        };

        /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 
        // 对齐父类
        // 
        template< int ALIGN_BYTE >
        class aligned_base_class
        {
        public:
            /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            // 
            // 为了对齐，重写了类的静态成员方法new和delete
            //
            static void operator delete(void* p) noexcept
            {
                aligned_alloc_and_free obj;
                obj.aligned_free(p);
            }
            static void* operator new(size_t size)
            {
                void* ptr = nullptr;
                {
                    aligned_alloc_and_free obj;
                    ptr = obj.aligned_alloc( size, ALIGN_BYTE );
                }
                if( !ptr )
                {
                    throw std::bad_alloc();
                }
                return ptr;
            }
            // 数组版本
            static void operator delete[]( void* p ) noexcept
            {
                operator delete(p);
            }
            static void* operator new[]( size_t size )
            {
                return operator new(size);
            }
        public:
            aligned_base_class()
            {
            }
            ~aligned_base_class()
            {
            }
        };
        /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 
        // 对齐包装类
        // 

        template< class T, int ALIGN_BYTE >
        class aligned_wrapper_class : public aligned_base_class<ALIGN_BYTE>
        {
        public:
            aligned_wrapper_class() : value(), padding{ 0 }
            {
            }
            ~aligned_wrapper_class()
            {
            }
        private:
            T value;
            char padding[(ALIGN_BYTE - sizeof( T )) % ALIGN_BYTE];
        public:
            T* operator->() { return &value; }
            operator T& () { return value; }
            T& obj() { return value; }
        };

        /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 
        // 容器节点
        // 
        template< class T >
        class lock_free_queue_container_item
        {
        public:
            using CONTAINER = lock_free_queue_container_item<T>;
        public:
            lock_free_queue_container_item() : next( 0 ), data( 0 )
            {
            }
            ~lock_free_queue_container_item()
            {
                delete_data();
                next = 0;
            }
        public:
            int delete_data()
            {
                int ret = 0;
                term_obj( data );
                return ret;
            }
        public:
            CONTAINER* next;
            T* data;
        };

        /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 
        // 容器节点池
        // 
        template< class CONTAINER, class Lock >
        class lock_free_container_pool
        {
        public:
            using CONTAINER_POOL = lock_free_container_pool<CONTAINER, Lock>;
        public:
            // 在队列启动时，会先以nullptr参数调用这个方法，来预分配内存
            // 获得扩展环形结构权限的线程，在开始扩展时，调用此方法得到此前保留的容器链表
            // 在完成扩展后，再次以nullptr参数调用这个方法，来提前申请好内存
            // 以便下次扩展时，可以直接拿到申请好的容器链表
            int init( CONTAINER ** head, CONTAINER ** tail )
            {
                int ret = 0;
                auto_lock<Lock> lock( &m_lock );
                int num = expand_step_num;
                if( first_init )
                {
                    first_init = false;
                    num = init_num;
                }
                CONTAINER *& pHead = container_list_head;
                CONTAINER *& pTail = container_list_tail;
                CONTAINER * pObj = 0;
                if( container_num < num )
                {
                    int alloc_num = num - container_num;
                    for( int i = 0; i < alloc_num; ++i )
                    {
                        init_obj( pObj );
                        if( !pHead )
                        {
                            pHead = pObj;
                        }
                        if( pTail )
                        {
                            pTail->next = pObj;
                        }
                        container_num++;
                        pTail = pObj;
                    }
                }
                ret = container_num;
                if( head && tail )
                {
                    *head = pHead;
                    *tail = pTail;
                    container_num = 0;
                    pHead = 0;
                    pTail = 0;
                }
                return ret;
            }
            // 释放这些保留内存
            int term()
            {
                int ret = 0;
                auto_lock<Lock> lock( &m_lock );
                CONTAINER *& pHead = container_list_head;
                CONTAINER *& pTail = container_list_tail;
                CONTAINER * pObj = pHead;
                CONTAINER * pT = 0;
                while( ( pT = pObj ) )
                {
                    pObj = pObj->next;
                    term_obj( pT );
                }
                container_num = 0;
                pHead = 0;
                pTail = 0;
                return ret;
            }
            CONTAINER * head()
            {
                return container_list_head;
            }
            CONTAINER * tail()
            {
                return container_list_tail;
            }
            int num()
            {
                return container_num;
            }
        public:
            lock_free_container_pool( int nInitNum, int nStep ) : container_list_head( 0 ),
                container_list_tail( 0 ),
                container_num( 0 ),
                first_init( true ),
                m_lock(),
                expand_step_num( nStep ),
                init_num( nInitNum )
            {
            }
            ~lock_free_container_pool()
            {
            }
        protected:
            CONTAINER * container_list_head;
            CONTAINER * container_list_tail;
            int container_num;
            bool first_init;
            Lock m_lock;
            int expand_step_num;
            int init_num;
        };

        /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 
        // 守卫节点
        // 
        template< class T, int ALIGNMENT >
        class lock_free_queue_guard_item
        {
        public:
            using GUARD = lock_free_queue_guard_item<T, ALIGNMENT>;
            using CONTAINER = typename lock_free_queue_container_item<T>::CONTAINER;
            using ATOMIC_GUARD = std::atomic<CONTAINER*>;
            using WRAPPER = aligned_wrapper_class<ATOMIC_GUARD, ALIGNMENT>;
        public:
            lock_free_queue_guard_item() : wrapper_ptr(0)
            {
                init_obj( wrapper_ptr );
            }
            ~lock_free_queue_guard_item()
            {
                term_obj( wrapper_ptr );
            }
        public:
            bool compare_exchange_store( CONTAINER* raw, CONTAINER* cur )
            {
                bool bQuit = (raw == cur);
                bool bRet = false;
                while( !bRet && !bQuit )
                {
                    CONTAINER* old = raw;
                    bRet = (*this)->compare_exchange_weak( old, cur, std::memory_order_release, std::memory_order_relaxed );
                    if( !bRet )
                    {
                        if( old != raw )
                        {
                            // 真失败，别人已经更新了
                            bQuit = true;
                        }
                        else
                        {
                            // 假失败
                        }
                    }
                    else
                    {
                        // 成功
                    }
                }
                return bRet;
            }
        public:
            ATOMIC_GUARD* operator->() { return &wrapper_ptr->obj(); }
            operator ATOMIC_GUARD& () { return wrapper_ptr->obj(); }
            ATOMIC_GUARD& obj() { return wrapper_ptr->obj(); }
        private:
            WRAPPER * wrapper_ptr;
        };

        /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 
        // 扩展标志
        // 
        template< int ALIGNMENT >
        class lock_free_queue_expand_tag
        {
        public:
            using TAG = lock_free_queue_expand_tag<ALIGNMENT>;
            using ATOMIC_TAG = std::atomic<bool>;
            using WRAPPER = aligned_wrapper_class<ATOMIC_TAG, ALIGNMENT>;
        public:
            lock_free_queue_expand_tag() : wrapper_ptr(0)
            {
                init_obj( wrapper_ptr );
            }
            ~lock_free_queue_expand_tag()
            {
                term_obj( wrapper_ptr );
            }
        public:
            bool compare_exchange_store( bool raw, bool cur )
            {
                bool bQuit = (raw == cur);
                bool bRet = false;
                while( !bRet && !bQuit )
                {
                    bool old = raw;
                    bRet = (*this)->compare_exchange_weak( old, cur, std::memory_order_release, std::memory_order_relaxed );
                    if( !bRet )
                    {
                        if( old != raw )
                        {
                            // 真失败，别人已经更新了
                            bQuit = true;
                        }
                        else
                        {
                            // 假失败
                        }
                    }
                    else
                    {
                        // 成功
                    }
                }
                return bRet;
            }
        public:
            ATOMIC_TAG* operator->() { return &wrapper_ptr->obj(); }
            operator ATOMIC_TAG& () { return wrapper_ptr->obj(); }
            ATOMIC_TAG& obj() { return wrapper_ptr->obj(); }
        private:
            WRAPPER * wrapper_ptr;
        };

        /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 
        // 无锁队列
        // 
        template< class T, class Lock >
        class lock_free_queue
        {
        public:
            /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            // 
            using CONTAINER = lock_free_queue_container_item<T>;
            using CONTAINER_POOL = lock_free_container_pool<CONTAINER, Lock>;
            using GUARD = lock_free_queue_guard_item<T, 128>;
            using TAG = lock_free_queue_expand_tag<128>;
        public:
            /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            // 
            // 帮助方法
            // 
            int expand_ring( CONTAINER* pTail, CONTAINER* pNext )
            {
                int ret = 0;

                CONTAINER* pAllocHead = 0;
                CONTAINER* pAllocTail = 0;

                // 如果竞争扩展权失败，返回
                if( 0 == ret )
                {
                    if( !tag.compare_exchange_store( false, true ) )
                    {
                        ret = 1;
                    }
                }
                // 读取预申请的链表
                if( 0 == ret )
                {
                    int num = m_container_pool.init( &pAllocHead, &pAllocTail );
                    if( 0 == num )
                    {
                        ret = 2;
                    }
                }
                // 开始扩展
                if( 0 == ret )
                {
                    pAllocTail->next = pNext;
                    std::atomic_thread_fence( std::memory_order_seq_cst );
                    pTail->next = pAllocHead;
                    m_pContainer->xos()->misc()->ensure_memory_visibility();
                }
                // 恢复扩展标志位
                if( 0 == ret )
                {
                    tag->store( false, std::memory_order_release );
                }
                // 再次预分配内存
                if( 0 == ret )
                {
                    m_container_pool.init( 0, 0 );
                }

                return ret;
            }
            int yield_thread()
            {
                int ret = 0;
                std::this_thread::yield();
                return ret;
            }
        public:
            /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            // 
            // push_back方法一定成功
            // 
            void push_back( T* pT )
            {
                CONTAINER* pHead = 0;
                CONTAINER* pTail = 0;
                CONTAINER* pNext = 0;
                bool bSuccess = false;
                while( !bSuccess )
                {
                    // 先检查是否正在扩展环形结构
                    {
                        bool bExpanding = tag->load( std::memory_order_acquire );
                        if( bExpanding )
                        {
                            yield_thread();
                            continue;
                        }
                    }
                    pHead = head->load( std::memory_order_acquire );
                    pTail = tail->load( std::memory_order_acquire );
                    pNext = pTail->next;
                    // 队列已满
                    if( pNext == pHead )
                    {
                        expand_ring( pTail, pNext );
                        yield_thread();
                        continue;
                    }
                    // next是否为空。如果不为空，说明是暂时的，需要循环检测
                    if( pNext->data )
                    {
                        yield_thread();
                        continue;
                    }
                    // 已经具备了竞争移动tail.tail.next的条件了
                    bSuccess = tail.compare_exchange_store( pTail, pNext );
                    if( bSuccess )
                    {
                        pTail->data = pT;
                    }
                }
            }
            T* pop_front()
            {
                CONTAINER* pHead = 0;
                CONTAINER* pTail = 0;
                CONTAINER* pNext = 0;
                T* pRet = 0;
                bool bSuccess = false;
                bool bQuit = false;
                while( !bSuccess && !bQuit )
                {
                    pHead = head->load( std::memory_order_acquire );
                    pTail = tail->load( std::memory_order_acquire );
                    pNext = pHead->next;
                    // 队列是否为空
                    if( pHead == pTail )
                    {
                        bQuit = true;
                        continue;
                    }
                    // head当前节点是否为空。如果为空，说明是暂时的，需要循环检测
                    if( !pHead->data )
                    {
                        yield_thread();
                        continue;
                    }
                    // 可以竞争移动head.head.next读数据了
                    bSuccess = head.compare_exchange_store( pHead, pNext );
                    if( bSuccess )
                    {
                        pRet = pHead->data;
                        pHead->data = 0;
                    }
                }
                return pRet;
            }
        protected:
            /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            // 
            int destroy_ring()
            {
                int ret = 0;
                CONTAINER* pHead = head->load( std::memory_order_acquire );
                CONTAINER* pItem = pHead->next;
                CONTAINER* pT = 0;
                while( (pT = pItem) && (pT != pHead) )
                {
                    pItem = pItem->next;
                    term_obj( pT );
                }
                term_obj( pHead );
                head->store( nullptr, std::memory_order_relaxed );
                tail->store( nullptr, std::memory_order_relaxed );
                m_container_pool.term();
                return ret;
            }
            int make_ring()
            {
                int ret = 0;
                CONTAINER* pHead = 0;
                CONTAINER* pTail = 0;
                m_container_pool.init( &pHead, &pTail );
                pTail->next = pHead;
                head->store( pHead, std::memory_order_relaxed );
                tail->store( pHead, std::memory_order_relaxed );
                m_container_pool.init( 0, 0 );
                return ret;
            }
        public:
            /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            // 
            int release_all()
            {
                int ret = 0;
                CONTAINER* pHead = head->load( std::memory_order_acquire );
                CONTAINER* pTail = tail->load( std::memory_order_acquire );
                CONTAINER* pT = 0;
                while( pHead != pTail )
                {
                    pT = pHead;
                    pHead = pHead->next;
                    pT->delete_data();
                }
                head->store( pTail, std::memory_order_relaxed );
                return ret;
            }
            int init( xos_container::i_container* pContainer )
            {
                int ret = 0;
                if( !m_pContainer )
                {
                    m_pContainer = pContainer;
                    make_ring();
                }
                return ret;
            }
            int term()
            {
                int ret = 0;
                if( m_pContainer )
                {
                    m_pContainer = 0;
                    destroy_ring();
                }
                return ret;
            }
        protected:
            /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            // 
            xos_container::i_container* m_pContainer;
            GUARD head;
            GUARD tail;
            TAG tag;
            CONTAINER_POOL m_container_pool;
        public:
            /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            //  
            lock_free_queue() : m_pContainer( 0 ), 
                head(), 
                tail(), 
                tag(), 
                m_container_pool( 10, 100 )
            {
            }
            ~lock_free_queue()
            {
                term();
            }
        };

    } // lock_free

} // xos_stl

#endif // __XOS_STL_POOL_LOCK_FREE_QUEUE_H__
